<!-- The documentation for conversion of some form of automaton to a grammar. -->

<HTML><HEAD> <TITLE>Automaton to Grammar Converters</TITLE> </HEAD><BODY>

<H1>Automaton to Grammar Converters</H1>

<CENTER><P><IMG SRC="images/fsa2grammar.png" ALT="Converting an FA to a Grammar" WIDTH="376" HEIGHT="267" BORDER="1"><BR>Incomplete conversion of an FA to a grammar</P></CENTER>

<P>To add the productions for an object, click on an object that corresponds to a production in the FA.  If a grammar production is selected, the object in the automaton that it was generated by will be highlighted.  Eventually all productions will be added, and the grammar may be exported.  For an FA, there will be exactly one production for every transition and final state.  For a PDA, there will be productions for only transitions, though there may be many of them.  Specialized notes for these two operations are written below.</P>

<P>The tool bar has some helpful controls:</P>

<DL>
<DT>Hint</DT>
<DD>This will convert one object (transition or, in the case of FA, final state) to the appropriate set of productions.</DD>

<DT>Show All</DT>
<DD>All remaining productions will be added.</DD>

<DT>What's Left?</DT>
<DD>All convertible but as yet unconverted objects will be highlighted.</DD>

<DT>Export</DT>
<DD>Once conversion has finished, the grammar may be output.</DD>
</DL>

<H2>FA to Grammar</H2>

<P>This operation converts a FA to a regular (specifically right linear) grammar.  This operation is featured in the window above.  Each state in the FA corresponds to a variable in the grammar, which is shown slung beneath each state.  The terminals for the grammar are the symbols on the transitions.</P>

<P>Each transition and each final state correspond to a production in the grammar, with finals states correspond to lambda productions, and for a transition of <VAR>a</VAR> between two states labeled <VAR>A</VAR> to <VAR>B</VAR>, the production <VAR>A <IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle"> aB</VAR> is added.</P>

<H2>PDA to Grammar</H2>

<p>The conversion from PDA to Context-Free Grammar requires that the PDA have a certain form before the conversion begins:</p>

<ul><li><p>only one final state</p></li>
<li><p>accepts only if stack is empty</p></li>
<li><p>each transition has the form: <VAR>a,A;</VAR> or <VAR>a,A;BC</VAR></p></li>
</ul>

<p>In the PDA transformation, all variables in the resulting Context Free Grammar (CFG) will be formed from two states and a symbol from the alphabet. In other words, one variable is represented in the form <VAR>q<SUB>i</SUB>Aq<SUB>j</SUB></VAR> where <VAR>i</VAR> and <VAR>j</VAR> are numbers corresponding to states in the PDA and <VAR>A</VAR> is a symbol in the alphabet of the PDA.</p>

<p>The actual rule generating begins with the starting rule. The variable for the starting rule is found by concatenating the initial state with the end of stack character(<VAR>Z</VAR>) and the beginning state.</P>

<P>For example, if an automata had an initial state <VAR>q<SUB>0</SUB></VAR> and a final state <VAR>q<SUB>3</SUB></VAR>, the starting rule would be <VAR>S<IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle">q<SUB>0</SUB>Zq<SUB>3</SUB></VAR>.</P>

<p>Once the starting state is established, the transitions must be processed. </p>

<ul> <li><p>Transitions of the form <VAR>a, A; <IMG SRC="entities/lambda.png" WIDTH="9" HEIGHT="12" ALIGN="middle"></VAR> from state <VAR>q<SUB>i</SUB></VAR> to state <VAR>q<SUB>j</SUB></VAR> are converted to <VAR>q<SUB>i</SUB>Aq<SUB>j</SUB><IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle">a</VAR></p>

</li> <li><p>Transitions of the form <VAR>a, A; BC</VAR> from state <VAR>q<SUB>i</SUB></VAR> to state <VAR>q<SUB>j</SUB></VAR> are converted to the set of rules:<BR>
{ <VAR>q<SUB>i</SUB>Aq<SUB>x</SUB></VAR> <IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle"> a (q<SUB>j</SUB>Bq<SUB>y</SUB>) (q<SUB>y</SUB>Cq<SUB>x</SUB>)</VAR> | <VAR>q<SUB>x</SUB></VAR> and <VAR>q<SUB>y</SUB></VAR> are states in the automaton}.</p> </li>

<P>When exporting, each of the <VAR>q<SUB>i</SUB>Aq<SUB>j</SUB></VAR> symbols has a single character variable substituted in its place.</P>

</BODY></HTML>
